package org.ala.linshen.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 一个括号字符串是一个 非空 且只包含 '(' 和 ')' 的字符串。如果下面 任意 条件为 真 ，那么这个括号字符串就是 合法的 。
 *
 * 字符串是 () 。
 * 字符串可以表示为 AB（A 连接 B），A 和 B 都是合法括号序列。
 * 字符串可以表示为 (A) ，其中 A 是合法括号序列。
 * 给你一个 m x n 的括号网格图矩阵 grid 。网格图中一个 合法括号路径 是满足以下所有条件的一条路径：
 *
 * 路径开始于左上角格子 (0, 0) 。
 * 路径结束于右下角格子 (m - 1, n - 1) 。
 * 路径每次只会向 下 或者向 右 移动。
 * 路径经过的格子组成的括号字符串是 合法 的。
 * 如果网格图中存在一条 合法括号路径 ，请返回 true ，否则返回 false 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
 * 输出：true
 * 解释：上图展示了两条路径，它们都是合法括号字符串路径。
 * 第一条路径得到的合法字符串是 "()(())" 。
 * 第二条路径得到的合法字符串是 "((()))" 。
 * 注意可能有其他的合法括号字符串路径。
 * 示例 2：
 *
 *
 *
 * 输入：grid = [[")",")"],["(","("]]
 * 输出：false
 * 解释：两条可行路径分别得到 "))(" 和 ")((" 。由于它们都不是合法括号字符串，我们返回 false 。
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 100
 * grid[i][j] 要么是 '(' ，要么是 ')' 。
 *
 * @author ala
 * @date 2024-09-24 11:43
 */
public class Q2267 {

    public static void main(String[] args) {
        Q2267 q = new Q2267();

//        char[][] grid = {{'(',')'},{'(',')'}};
//        char[][] grid = {{'(','(','('},{')','(',')'},{'(','(',')'},{'(','(',')'}};
//        char[][] grid = {{')',')'},{'(','('}};
        char[][] grid = {{'('},{')'}};

        System.out.println(q.hasValidPath(grid));
    }

    public boolean hasValidPath(char[][] grid) {
        return V1(grid);
    }
    static int INF = Integer.MIN_VALUE >> 1;
    /**
     *  1）dp[i][j] = List<Integer>表示(i,j)点为结尾时，所有路径中左括号的数量
     *      dp[i][j] = [dp[i-1][j] × grid[i][j], dp[i][j-1] × grid[i][j]]
     *      但要剔除掉其中已经 < 0 的值
     *      List中有一个值，就代表有一条路径，该路径走到(i,j)时左括号的数量
     *      如果dp[i][j]的List为空，说明从(0,0)点走到(i,j)，无论选哪条路径都是死路
     *  2）如果某一行全是死路，直接返回false
     *  3）如果走到右下，判断List中是否存在值为0的路径
     */
    protected boolean V1(char[][] grid) {
        int M = grid.length, N = grid[0].length;

        List<Integer>[][] dp = new List[M + 1][N + 1];
        for (int i = 1 ; i <= M ; i++) {
            dp[i][0] = Arrays.asList(INF);
        }
        for (int j = 1 ; j <= N ; j++) {
            dp[0][j] = Arrays.asList(INF);
        }

        for (int i = 1 ; i <= M ; i++) {
            //  该行是否全g
            boolean allG = true;
            for (int j = 1 ; j <= N ; j++) {
                int v = grid[i - 1][j - 1] == '(' ? 1 : -1;
                dp[i][j] = new ArrayList<>();
                if (i == 1 && j == 1) {
                    if (v == -1) {return false;}
                    else { dp[i][j].add(1); }
                    allG = false;
                    continue;
                }

                //  相同的值进一步压缩（M + N其实多了一个点，但作为数组长度，没差）
                boolean[] vis = new boolean[M + N];
                //  来自上边的路径
                for (int _v : dp[i - 1][j]) {
                    int sum = v + _v;
                    if (sum >= 0 && !vis[sum]) {
                        dp[i][j].add(sum);
                        allG = false;
                        vis[sum] = true;
                    }
                }
                //  来自左边的路径
                for (int _v : dp[i][j - 1]) {
                    int sum = v + _v;
                    if (sum >= 0 && !vis[sum]) {
                        dp[i][j].add(sum);
                        allG = false;
                        vis[sum] = true;
                    }
                }
            }
            //  如果某一行全g了，直接返回false
            if (allG) {return false;}
        }
        //  判断最后一行是否有为0的路径
        for (int v : dp[M][N]) {
            if (v == 0) {return true;}
        }
        return false;
    }
}
